#include <vector>
#include <queue>
using namespace std;
class Solution {
    int n,m;
    queue<pair<int,int> > q;
    vector<bool> visited;

    void bfs(vector<vector<char> > &board, int x, int y, char fill) {
        q.push(make_pair(x,y));
        while (!q.empty()) {
            int x0=q.front().first, y0=q.front().second;
            q.pop();
            board[x0][y0]=fill;
            for (int k=0;k<4;k++) {
                const int way[4][2]={-1,0, 1,0, 0,1, 0,-1};
                int x=x0+way[k][0], y=y0+way[k][1];
                if (0<=x && x<n && 0<=y && y<m && board[x][y]=='O') {
                    q.push(make_pair(x,y));
                    board[x][y]=fill;
                }
            }
        }
    }
public:
    void solve(vector<vector<char> > &board) {
        n=board.size();
        m=0;
        if (n>0) m=board[0].size();
        if (n==0 || m==0) return;
        for (int i=0;i<n;i++) {
            if (board[i][0]=='O') bfs(board,i,0,'o');
            if (board[i][m-1]=='O') bfs(board,i,m-1,'o');
        }
        for (int i=0;i<m;i++) {
            if (board[0][i]=='O') bfs(board,0,i,'o');
            if (board[n-1][i]=='O') bfs(board,n-1,i,'o');
        }
        for (int i=1;i<n-1;i++)
            for (int j=1;j<m-1;j++)
                if (board[i][j]=='O') bfs(board,i,j,'X');
        for (int i=0;i<n;i++)
            for (int j=0;j<m;j++)
                if (board[i][j]=='o') board[i][j]='O';
    }
};
